//
// GPSMapEdit
// (c) Konstantin Galichsky (kg@geopainting.com), 2005-2007
// (c) Denis Perchine (dyp@perchine.com), 2005
// (c) Nikita Karnauhov (jinx@navitel.su), 2007
//
// Verify map.
//

# include "StdAfx.h"
# include "Resource.h"
# include "VerifyMap.h"
# include "Map.h"
# include "MapView.h"
# include "Position.h"
# include "Scale.h"
# include "Log.h"
# include "Status.h"
# include "PtAlgo.h"
# include "Load.h"
# include "Levels.h"
# include "Types.h"
# include "ShowRgnOnMap.h"
# include "Dialog.h"
# include "Distance.h"
# include "PrintUnits.h"
# include "ListView.h"
# include "Settings.h"
# include "fast_floor.h"
# include "Wrappers.h"
# include "Globals.h"

enum {
	ilcType  = 0,
	ilcLabel = 1,
	ilcLevel = 2,
	ilcPos   = 3,
	ilcRev   = 4,
	ilcMsg   = 5,
};

struct vr_item_t {
	const char * strWarning;
	const rgn_t * pRgn;
	size_t cLevel;
	point_t ptError;
	rect_t rectContext;
	bool bReviewed;
};

typedef std::vector<vr_item_t> vritems_t;

static vritems_t g_vecVRItems;
static size_t g_cVRItemSelected = -1;

static
void _AddMessageToList (
	const char * _strWarning,
	const rgn_t * _pRgn, size_t _cLevel, const point_t & _pt, const rect_t & _rect
) {
	g_vecVRItems.push_back (vr_item_t ());

	vr_item_t & data = g_vecVRItems.back ();
	data.strWarning  = _strWarning;
	data.pRgn        = _pRgn;
	data.cLevel      = _cLevel;
	data.ptError     = _pt;
	data.rectContext = _rect;
	data.bReviewed   = false;
}

////////////////////////////////////////////////

struct vm_t {
	bool bCheckPolygons;
	bool bCheckRPolylines;
	bool bCheckNodes;
	bool bCheckNotConnectedNodes;
	float fMinNodeDistance;
};
static void _DoVerifyMap (const vm_t & _vm);

////////////////////////////////////////////////

namespace {
	struct LessType {
		LessType (bool _bAscending) : m_bAscending (_bAscending) {}

		bool operator () (const vr_item_t & _i1, const vr_item_t & _i2) {
			const ULONG ulType1 = _i1.pRgn ? _i1.pRgn->ushType + ULONG (_i1.pRgn->Kind << 16) : -1;
			const ULONG ulType2 = _i2.pRgn ? _i2.pRgn->ushType + ULONG (_i2.pRgn->Kind << 16) : -1;
			const int iCmp = ulType1 - ulType2;
			return m_bAscending ? iCmp < 0 : iCmp > 0;
		}

	  private:
		const bool m_bAscending;
	};

	struct LessLbl {
		LessLbl (bool _bAscending) : m_bAscending (_bAscending) {}

		bool operator () (const vr_item_t & _i1, const vr_item_t & _i2) {
			const int iCmp = ::lstrcmp (
				_i1.pRgn ? _i1.pRgn->strLabel.c_str () : "",
				_i2.pRgn ? _i2.pRgn->strLabel.c_str () : ""
			);
			return m_bAscending ? iCmp < 0 : iCmp > 0;
		}

	  private:
		const bool m_bAscending;
	};

	struct LessRev {
		LessRev (bool _bAscending) : m_bAscending (_bAscending) {}

		bool operator () (const vr_item_t & _i1, const vr_item_t & _i2) {
			const int iCmp = _i1.bReviewed - _i2.bReviewed;
			return m_bAscending ? iCmp < 0 : iCmp > 0;
		}

	  private:
		const bool m_bAscending;
	};

	struct LessMsg {
		LessMsg (bool _bAscending) : m_bAscending (_bAscending) {}

		bool operator () (const vr_item_t & _i1, const vr_item_t & _i2) {
			const int iCmp = ::lstrcmp (_i1.strWarning, _i2.strWarning);
			return m_bAscending ? iCmp < 0 : iCmp > 0;
		}

	  private:
		const bool m_bAscending;
	};

	struct LessLevel {
		LessLevel (bool _bAscending) : m_bAscending (_bAscending) {}

		bool operator () (const vr_item_t & _i1, const vr_item_t & _i2) {
			const int iCmp = _i1.cLevel - _i2.cLevel;
			return m_bAscending ? iCmp < 0 : iCmp > 0;
		}

	  private:
		const bool m_bAscending;
	};

	struct LessPos {
		LessPos (bool _bAscending) : m_bAscending (_bAscending) {}

		bool operator () (const vr_item_t & _i1, const vr_item_t & _i2) {
			const int iCmp = _i1.ptError.y < _i2.ptError.y ? -1 : 1;
			return m_bAscending ? iCmp < 0 : iCmp > 0;
		}

	  private:
		const bool m_bAscending;
	};
}

///////////////////////////////////////////////

class CInvalidList : public CDialog {
  public:
	CInvalidList () : CDialog (IDD_VERIFY_REPORT) {}

	// Override.
	virtual bool OnInit (HWND _hwndFocus);
	virtual void OnDestroy ();
	virtual void OnCommand (WORD _wCmd, WORD _wNotifyCode, HWND _hwndCtl);
	virtual bool OnNotify (int _idCtrl, NMHDR * _pInfo);

	static CInvalidList * s_pInvalidList;

  private:
	CListView m_List; // IDC_LIST

	void _GetItemText (
		const vr_item_t & _data, size_t _cColumn,
		char * _strBuf, size_t _cSize
	);

	rect_t _CropRect (const rect_t & _rectSrc, const point_t & _ptFocus);

	void _LocateSel ();
	void _Sort ();
	void _FillItems ();
};

void CInvalidList::_Sort () {
	switch (m_List.GetSortingColumn ()) {
		case -1:
			break;

		case ilcType:  std::sort (g_vecVRItems.begin (), g_vecVRItems.end (), LessType  (m_List.IsSortingAscending ())); break;
		case ilcLabel: std::sort (g_vecVRItems.begin (), g_vecVRItems.end (), LessLbl   (m_List.IsSortingAscending ())); break;
		case ilcLevel: std::sort (g_vecVRItems.begin (), g_vecVRItems.end (), LessLevel (m_List.IsSortingAscending ())); break;
		case ilcPos:   std::sort (g_vecVRItems.begin (), g_vecVRItems.end (), LessPos   (m_List.IsSortingAscending ())); break;
		case ilcRev:   std::sort (g_vecVRItems.begin (), g_vecVRItems.end (), LessRev   (m_List.IsSortingAscending ())); break;
		case ilcMsg:   std::sort (g_vecVRItems.begin (), g_vecVRItems.end (), LessMsg   (m_List.IsSortingAscending ())); break;

		default:
			assert (false);
			break;
	}

	// NOTE: this does not sort virtual list view indeed, but it shows sorting arrows in the header.
	m_List.Sort ();

	ListView_SetItemCount (m_List, g_vecVRItems.size ());
}

void CInvalidList::_FillItems () {
	if (g_vecVRItems.size () > 20000)
		// NOTE: avoid first long sorting.
		m_List.SetSortingColumn (-1);
	_Sort ();

	if (g_cVRItemSelected != -1) {
		SetSelection           (m_List, g_cVRItemSelected);
		ListView_EnsureVisible (m_List, g_cVRItemSelected, FALSE);
	} else
		SetSelection           (m_List, -1);
}

bool CInvalidList::OnInit (HWND _hwndFocus) {
	// Start.
	SetFocus (IDC_START);

	// Settings.
	CheckDlgButton (IDC_POLYGONS,        GetSetting ("CheckPolygons",   true));
	CheckDlgButton (IDC_RPOLYLINES,      GetSetting ("CheckRPolylines", true));
	CheckDlgButton (IDC_NODES,           GetSetting ("CheckNodes",      true));
	CheckDlgButton (IDC_TOO_CLOSE_NODES, GetSetting ("CheckCloseNodes", true));

	// Locate.
	EnableDlgItem (IDC_LOCATE, false);

	// Results.
	m_List.Init (m_hWnd, IDC_LIST, "VerifyReport");
	m_List.SetExtStyle (LVS_EX_FULLROWSELECT | LVS_EX_HEADERDRAGDROP);

	m_List.SetImageList (g_map.pTypeSet->GetTypeIcons (), true);

	AddColumn (m_List, ilcType,  "Type");
	AddColumn (m_List, ilcLabel, "Label");
	AddColumn (m_List, ilcLevel, "Level");
	AddColumn (m_List, ilcPos,   "Position");
	AddColumn (m_List, ilcRev,   "Rev");
	AddColumn (m_List, ilcMsg,   "Warning");

	AutoSizeColumns (m_List);
	ListView_SetColumnWidth (m_List, ilcType,  200);
	ListView_SetColumnWidth (m_List, ilcLabel, 250);
	m_List.LoadHeaders ();

	_FillItems ();

	return false;
}

void CInvalidList::OnDestroy () {
	g_cVRItemSelected = ListView_GetSelectionMark (m_List);

	m_List.SaveHeaders ();
	m_List.Destroy ();
}

void CInvalidList::_LocateSel () {
	const size_t cSel = ListView_GetSelectionMark (m_List);
	if (cSel >= g_vecVRItems.size ())
		return;
	vr_item_t & data = g_vecVRItems [cSel];
	if (data.pRgn == NULL || data.pRgn->IsDeleted ())
		return;

	data.bReviewed = true;
	ListView_Update (m_List, cSel);

	if (data.pRgn)
		ShowRgnOnMap (* data.pRgn);

	const rect_t rect = _CropRect (data.rectContext, data.ptError);

	SetScale (GetRectScale (rect), false);
	SetToCenter (point_t (rect.MeanX (), rect.MeanY ()));
	SetVisibleLevel (data.cLevel);

	Refresh ();
}

void CInvalidList::OnCommand (WORD _wCmd, WORD _wNotifyCode, HWND _hwndCtl) {
	switch (_wCmd) {
		case IDC_START: {
			g_cVRItemSelected = -1;
			g_vecVRItems.clear ();
			_FillItems ();

			vm_t vm;
			vm.bCheckPolygons   = IsDlgButtonChecked (IDC_POLYGONS);
			vm.bCheckRPolylines = IsDlgButtonChecked (IDC_RPOLYLINES);
			vm.bCheckNodes      = IsDlgButtonChecked (IDC_NODES);
			vm.bCheckNotConnectedNodes = false;
			vm.fMinNodeDistance = IsDlgButtonChecked (IDC_TOO_CLOSE_NODES) ? 5.4 : 0;
			
			_DoVerifyMap (vm);

			if (g_vecVRItems.empty ())
				InfoMsgBox ("No invalid regions found.\n");

			_FillItems ();

			break;
		}

		case IDC_LOCATE:
			_LocateSel ();
			break;

		case IDCANCEL:
			SaveSetting ("CheckPolygons",   IsDlgButtonChecked (IDC_POLYGONS));
			SaveSetting ("CheckRPolylines", IsDlgButtonChecked (IDC_RPOLYLINES));
			SaveSetting ("CheckNodes",      IsDlgButtonChecked (IDC_NODES));
			SaveSetting ("CheckCloseNodes", IsDlgButtonChecked (IDC_TOO_CLOSE_NODES));

			//EndDialog (0);
			Hide ();
			break;
	}
}

bool CInvalidList::OnNotify (int _idCtrl, NMHDR * _pInfo) {
	switch (_pInfo->code) {
		case NM_RCLICK:
			m_List.PopupMenu_OnHeaderRClick (_pInfo);
			break;

		case LVN_COLUMNCLICK: {
			if (_idCtrl != IDC_LIST)
				break;

			// Save selection.
			const size_t cSel = ListView_GetSelectionMark (m_List);
			const LPARAM lParamSel = cSel == -1 ? -1 : GetLParam (m_List, cSel);

			m_List.Sort_OnColumnClick (_pInfo);
			_Sort ();

			// Restore selection.
			if (lParamSel != -1)
				m_List.SelectByLParam (lParamSel);

			break;
		}

		case LVN_GETDISPINFO: {
			if (_idCtrl != IDC_LIST)
				break;

			NMLVDISPINFO * const pInfo2 = reinterpret_cast<NMLVDISPINFO *> (_pInfo);
			LVITEM & lvi = pInfo2->item;
			if ((size_t) lvi.iItem >= g_vecVRItems.size ())
				break;
			const vr_item_t & data = g_vecVRItems [lvi.iItem];

			if (lvi.mask & LVIF_TEXT)
				_GetItemText (data, lvi.iSubItem, lvi.pszText, lvi.cchTextMax);
			if (lvi.mask & LVIF_IMAGE)
				lvi.iImage = data.pRgn ? data.pRgn->GetTypeDesc ()->cImageListIndex : -1;

			return true;
		}

		case LVN_ITEMCHANGED: {
			if (_idCtrl != IDC_LIST)
				break;

			const NMLISTVIEW * const pInfo2 = reinterpret_cast<const NMLISTVIEW *> (_pInfo);
			if (pInfo2->uNewState & LVIS_SELECTED) {
				if ((size_t) pInfo2->iItem >= g_vecVRItems.size ())
					break;
				const vr_item_t & data = g_vecVRItems [pInfo2->iItem];

				EnableDlgItem (IDC_LOCATE, data.pRgn && ! data.pRgn->IsDeleted ());
			}

			break;
		}

		case NM_RETURN:
		case NM_DBLCLK: {
			if (_idCtrl != IDC_LIST)
				break;

			_LocateSel ();
			break;
		}
	}

	return false;
}

rect_t CInvalidList::_CropRect (const rect_t & _rectSrc, const point_t & _ptFocus) {
	rect_t rect = _rectSrc;

	if (rect.Width () > 2*rect.Height ()) {
		rect.x0 = _ptFocus.x - rect.Height ();
		rect.x1 = _ptFocus.x + rect.Height ();
	} else if (rect.Height () > 2*rect.Width ()) {
		rect.y0 = _ptFocus.y - rect.Width ();
		rect.y1 = _ptFocus.y + rect.Width ();
	}

	rect.Shift (_ptFocus.x - rect.MeanX (), _ptFocus.y - rect.MeanY ());

	return rect;
}

void CInvalidList::_GetItemText (const vr_item_t & _data, size_t _cColumn, char * _strBuf, size_t _cSize) {
	if (_data.pRgn && _data.pRgn->IsDeleted ()) {
		::strncpy (_strBuf, "(deleted)", _cSize);
		return;
	}

	switch (_cColumn) {
		case ilcType:  ::strncpy     (_strBuf, _data.pRgn && _data.pRgn->GetTypeDesc () ? _data.pRgn->GetTypeDesc ()->strTypeName : "-", _cSize); break;
		case ilcLabel: ::strncpy     (_strBuf, _data.pRgn && _data.pRgn->strLabel.empty () ? "-" : _data.pRgn->strLabel.c_str (), _cSize); break;
		case ilcLevel: ::_snprintf   (_strBuf, _cSize, "%d", _data.cLevel); break;
		case ilcPos:   PrintPosition (_strBuf, _data.ptError); break;
		case ilcRev:   ::strncpy     (_strBuf, _data.bReviewed ? "Y" : "-", _cSize); break;
		case ilcMsg:   ::strncpy     (_strBuf, _data.strWarning, _cSize); break;
	}
}

////////////////////////////////////////

void ResetVerifyMapResults () {
	CCritSec::CLock lock (g_cs);

	g_vecVRItems.clear ();
	g_cVRItemSelected = -1;
}

CInvalidList * CInvalidList::s_pInvalidList;

void VerifyMap () {
	CCritSec::CLock lock (g_cs);

//	CInvalidList dlg;
//	dlg.ShowModal (g_hWnd);
	ShowModeless (CInvalidList::s_pInvalidList, g_hWnd);
}

static
void _DoVerifyMap (const vm_t & _vm) {
	CCritSec::CLock lock (g_cs);

	const size_t cTotalRgns = g_map.layers [rkPolyline].cRgns + g_map.layers [rkPolygon].cRgns;
	if (cTotalRgns == 0)
		return;
	size_t cRgnsProcessed = 0;
	SetStatus (GetStr (IDS_STATUS_VERIFYING));
	SetProgressStatus (0);

	for (rgnodes_t::iterator i = g_map.rgnodes.begin (); i != g_map.rgnodes.end (); ++ i) {
		rgnode_t & node = * i;
		node.pExtra = NULL;
	}

	const size_t cLevels = g_map.Levels.size ();
	int nKind;
	for (nKind = 0; nKind < rkMax; ++ nKind) {
		const rgns_t & rgns = g_map.layers [nKind].rgns;
		if (nKind == rkPoint)
			continue;

		for (rgns_t::const_iterator iRgn = rgns.begin (); iRgn != rgns.end (); ++ iRgn) {
			const rgn_t & rgn = * iRgn;
			if (rgn.IsDeleted () || rgn.IsWTR ())
				continue;

			const bool bPolygon = rgn.IsPolygon ();
			const bool bRPolyline = nKind == rkPolyline && rgn.HasRGNodes () && g_map.pTypeSet->pfIsRoad (rgn);
			if (! bPolygon && ! bRPolyline)
				continue;

			const rgn_elements_t & elements = rgn.elements;
			const size_t cElements = elements.size ();

			bool bCheckContour = true;
			if (! _vm.bCheckRPolylines && bRPolyline)
				bCheckContour = false;
			if (! _vm.bCheckPolygons && bPolygon)
				bCheckContour = false;

			if (bCheckContour) {
				for (size_t cElement1 = 0; cElement1 < cElements; ++ cElement1) {
					const rgn_element_t & element1 = elements [cElement1];
					if (element1.bDeleted)
						continue;

					if (element1.cLevel >= cLevels)
						continue;

					const points_t & points1 = element1.points;

					for (size_t cElement2 = cElement1; cElement2 < cElements; ++ cElement2) {
						const rgn_element_t & element2 = elements [cElement2];
						if (element2.bDeleted)
							continue;

						if (element2.cLevel >= cLevels)
							continue;
						if (element2.cLevel != element1.cLevel)
							continue;

						const points_t & points2 = element2.points;

						if (bRPolyline) {
							pip_info_t pip_info;
							bool bIntersects;
							if (cElement2 == cElement1)
								bIntersects = PolylineIntersectsSelfInNode (points1, & pip_info);
							else {
								bIntersects = PolylineIntersectsPolylineInNode (points1, points2, & pip_info);
								if (bIntersects) {
									const bool bEnd1 = pip_info.cSegment1 == 0 || pip_info.cSegment1 + 1 == points1.size ();
									const bool bEnd2 = pip_info.cSegment2 == 0 || pip_info.cSegment2 + 1 == points2.size ();
									if (bEnd1 && bEnd2)
										bIntersects = false;
								}
							}
							if (bIntersects) {
								const point_t & pt = points1 [pip_info.cSegment1];
								const rect_t rect (pt.x - 50e-5f, pt.y - 50e-5f, pt.x + 50e-5f, pt.y + 50e-5f);

								_AddMessageToList (
									"Routable polyline intersects itself",
									& rgn, element1.cLevel, pt, rect
								);
							}
						} else if (bPolygon) {
							pip_info_t pip_info;
							if (PolylineIntersectsPolyline (points1, points2, bPolygon, & pip_info)) {
								const point_t & p1b = points1 [pip_info.cSegment1];
								const point_t & p1e = points1 [pip_info.cSegment1 + 1 < points1.size () ? pip_info.cSegment1 + 1 : 0];
								const point_t & p2b = points2 [pip_info.cSegment2];
								const point_t & p2e = points2 [pip_info.cSegment2 + 1 < points2.size () ? pip_info.cSegment2 + 1 : 0];

								rect_t rect (p1b.x, p1b.y, p1b.x, p1b.y);
								rect.Extend (p1e);
								rect.Extend (p2b);
								rect.Extend (p2e);

								const double d = (p2e.y - p2b.y)*(p1e.x - p1b.x) - (p2e.x - p2b.x)*(p1e.y - p1b.y);
								double u = (p2e.x - p2b.x)*(p1b.y - p2b.y) - (p2e.y - p2b.y)*(p1b.x - p2b.x);
								assert (d != 0);
								if (d != 0)
									u /= d;
								const point_t ptCross (p1b.x + u*(p1e.x - p1b.x), p1b.y + u*(p1e.y - p1b.y));

								_AddMessageToList (
									"Polygon contour intersects itself",
									& rgn, element1.cLevel, ptCross, rect
								);
							}
						}
					}
				}
			}

			// Check nodes.
			if ((_vm.bCheckNodes || _vm.bCheckNotConnectedNodes || _vm.fMinNodeDistance > 0) && nKind == rkPolyline) {
				for (size_t cElement = 0; cElement < cElements; ++ cElement) {
					const rgn_element_t & element = elements [cElement];
					if (element.bDeleted)
						continue;

					if (element.pExtra) {
						// Nodes.
						const point_extras_t & PointExtras = element.pExtra->PointExtras;
						const size_t cPoints = PointExtras.size ();
						const points_t & points = element.points;
						size_t cPrevNode = -1;
						for (size_t cPoint = 0; cPoint < cPoints; ++ cPoint) {
							const rgnode_t * const pRGNode = PointExtras [cPoint].GetRGNode ();
							if (pRGNode == NULL)
								continue;

							const point_t & pt = points [cPoint];

							if (_vm.bCheckNodes) {
								const point_t * const pPoint = pRGNode->pExtra != NULL ? reinterpret_cast<const point_t *> (pRGNode->pExtra) : NULL;
								if (pPoint != NULL && ! (* pPoint == pt)) {
									const rect_t rect (pt.x - 50e-5f, pt.y - 50e-5f, pt.x + 50e-5f, pt.y + 50e-5f);

									_AddMessageToList (
										"Misaligned node",
										& rgn, element.cLevel, pt, rect
									);
								}
								if (pRGNode->pExtra == NULL)
									pRGNode->pExtra = const_cast<point_t *> (& pt);
							}

							if (_vm.bCheckNotConnectedNodes && pRGNode->btPolylines < 2) {
								const rect_t rect (pt.x - 50e-5f, pt.y - 50e-5f, pt.x + 50e-5f, pt.y + 50e-5f);

								_AddMessageToList (
									"Not connected node",
									& rgn, element.cLevel, pt, rect
								);
							}

							if (_vm.fMinNodeDistance > 0) {
								if (cPrevNode != -1) {
									const float fD = GetLength (points, cPrevNode, cPoint + 1)*40e6f/360.f;
									if (fD <= _vm.fMinNodeDistance) {
										const rect_t rect (pt.x - 50e-5f, pt.y - 50e-5f, pt.x + 50e-5f, pt.y + 50e-5f);

										_AddMessageToList (
											"Too close nodes",
											& rgn, element.cLevel, pt, rect
										);
									}
								}
								cPrevNode = cPoint;
							}
						}
					}
				}
			}

			if (g_bStop) {
				WarningMsgBox ("Operation cancelled.\n");
				return;
			}

			++ cRgnsProcessed;
			SetProgressStatus (cRgnsProcessed*100/cTotalRgns);
		}
	}

	SetStatusReady ();
}

//////////////////////////////////////////////////////////////////////////

static
float _FindNearestNode (
	const map_t & _map, const rgnode_t * const pNode, const point_t & pt, 
	point_t & ptOut
) {
	float fDistance = 1e10;
	const layer_t & layer = _map.layers [rkPolyline];

	for (rgns_t::const_iterator ri = layer.rgns.begin (); ri != layer.rgns.end (); ++ ri) {
		const rgn_t & rgn = * ri;
		for (rgn_elements_t::const_iterator ei = rgn.elements.begin (); ei != rgn.elements.end (); ++ ei) {
			const rgn_element_t & element = * ei;
			if (!element.pExtra)
				continue;

			const double c_fE = 360.f/(1 << _map.Levels [element.cLevel].btBits); 
			const points_t & points = element.points;
			const point_extras_t & extras = element.pExtra->PointExtras;
			
			const size_t cPoints = points.size ();
			for (size_t cPoint = 0; cPoint < cPoints; ++ cPoint) {
				if (extras[cPoint].empty ())
					continue;
				if (extras[cPoint].GetRGNode () == pNode)
					continue;
				if (!extras[cPoint].GetRGNode ()->bIsExternal)
					continue;
				
				const point_t & point = points [cPoint];
				
				const float fD = Distance (pt, point);
				if (fD < fDistance) {
					fDistance = fD;
					ptOut = point;
				}
			}
		}
	}
	
	return fDistance;
}

// Calculate minimal distance between external nodes
void CalcMinNodeDistance (map_t & _map) {
	// Ensure that node counters are correct.
	_map.CountRGNodes (true);
	
	float fDistance = 1e10;
	bool bFound = false;

	point_t pt1;
	point_t pt2;
	
	SetStatus (GetStr (IDS_STATUS_CALCULATING));
	SetProgressStatus (0);

	const layer_t & layer = _map.layers[rkPolyline];
	const size_t cTotalRgns = layer.cRgns;
	size_t cRgnsProcessed = 0;
	int lastProgress = 0;

	for (rgns_t::const_iterator ri = layer.rgns.begin (); ri != layer.rgns.end (); ++ ri) {
		const int progress = (cRgnsProcessed++)*100/cTotalRgns;
		if (progress > lastProgress) {
			SetProgressStatus (progress);
			lastProgress = progress;
		}
		
		const rgn_t & rgn = * ri;
		for (rgn_elements_t::const_iterator ei = rgn.elements.begin (); ei != rgn.elements.end (); ++ ei) {
			const rgn_element_t & element = * ei;
			if (!element.pExtra)
				continue;
			
			const double c_fE = 360.f/(1 << _map.Levels [element.cLevel].btBits); 
			
			const points_t & points = element.points;
			const point_extras_t & extras = element.pExtra->PointExtras;
			
			const size_t cPoints = points.size ();
			for (size_t cPoint = 0; cPoint < cPoints; ++ cPoint) {
				if (extras[cPoint].empty ())
					continue;
				if (!extras[cPoint].GetRGNode ()->bIsExternal)
					continue;
				
				const point_t & point = points [cPoint];
				
				const float fD = _FindNearestNode (_map, extras[cPoint].GetRGNode (), point, pt1);
				if (::fabs(fD) > 1e-3 && (fD < fDistance || !bFound)) {
					fDistance = fD;
					pt2 = point;
					bFound = true;
				}
			}
		}
	}

	SetStatusReady ();

	if (bFound)
		InfoMsgBox ("Minimal distance = %.6f", fDistance);
	else
		InfoMsgBox ("Map does not have external nodes at all\nor has only one external node.");
}
